package com.cdream.basic.algorithm.leetcode.dfs;

import java.util.List;

/**
 * 回溯超时了！！！
 *
 * @author cdream
 * @date 6/6/21
 */

public class Question474 {
    private int maxCount = 0;
    private int[] lenArray;

    public static void main(String[] args) {
        System.out.println(new Question474().findMaxForm2(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3));
    }

    public int findMaxForm2(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 1; i <= strs.length; i++) {
            int count0 = count0(strs[i - 1]);
            int count1 = strs[i - 1].length() - count0;
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    if (j >= count0 && k >= count1) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count0][k - count1] + 1);
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];

    }

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (int i = 0; i < strs.length; i++) {
            int count0 = count0(strs[i]);
            int count1 = strs[i].length() - count0;
            for (int j = m; j >= count0; j--) {
                for (int k = n; k >= count1; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count0][k - count1] + 1);
                }
            }
        }
        return dp[m][n];

    }


    public int count0(String s) {
        int count0 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                count0++;
            }
        }
        return count0;
    }

    private void backTrace(String[] strs, int index, int m, int n, List<String> midList) {
        if (index == strs.length) {
            maxCount = Math.max(midList.size(), maxCount);
            return;
        }


        backTrace(strs, index + 1, m, n, midList);

        String str = strs[index];
        int count1 = 0;
        int count0 = 0;
        for (char c : str.toCharArray()) {
            if (c == '1') {
                count1++;
            } else {
                count0++;
            }
        }
        if (m < count0 || n < count1) {
            maxCount = Math.max(midList.size(), maxCount);
            return;
        }
        midList.add(str);
        backTrace(strs, index + 1, m - count0, n - count1, midList);
        midList.remove(midList.size() - 1);
    }
}
